/**
 * 二叉树转双向链表
 */

public class Solution2 {
    private static TreeNode tail = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        tail = null;
        return creatLinkedList(pRootOfTree);
    }

    //返回值为当前双向链表的头节点
    //方法内部做三件事，确定新链表的头节点，确定新链表的尾节点，确定当前节点对于前后节点的指向
    private TreeNode creatLinkedList(TreeNode root) {
        if(root == null) {
            return null;
        }
        //如何判断头节点，如果当前左子树有节点，那么就返回左子树返回的头节点
        //如果左子树没有节点了，那么我们的头节点就是自身
        TreeNode head = null;
        //确定新链表的头节点
        if(root.left == null) {
            head = root;
        }else {
            head = creatLinkedList(root.left);
        }
        //root的prev就应该指向tail，无论tail是null还是节点
        root.left = tail;
        //如果tail不是null，那么tail的next也应该指向root
        //此时root与它前面的节点的关系已经确定出来了
        //而root和它之后节点的指向，由下一个节点考虑
        //如果当前节点就是最后一个节点，那么一定是它自身右子树没有节点了，而此时root的right本身就是null，也不需要修改
        if(tail != null) {
            tail.right = root;
        }
        //root设为新的tail节点
        tail = root;
        //必须在尾节点更新为root时，才能遍历右子树
        creatLinkedList(root.right);
        return head;
    }
}